package topcoder;

public class ArcadeManao {

	void updatePlatform(int i, int j, int l, String[] S, int[][] B, int n, int m) {
		int x;
		
		B[i][j] = l;
		updateNeighbors(i, j, S, B, n, m);
		
		if (j < m - 1) {
			x = j + 1;
			while(x < m && S[i].charAt(x) == 'X') {
				if (l < B[i][x]) {
					B[i][x] = l;
					updateNeighbors(i, x, S, B, n, m);
				}
				x++;
			}
		}
		
		if (j > 0) {
			x = j - 1;
			while(x >= 0 && S[i].charAt(x) == 'X') {
				if (l < B[i][x]) {
					B[i][x] = l;
					updateNeighbors(i, x, S, B, n, m);
				}
				x--;
			}
		}
	}
	
	void updateNeighbors(int i, int j, String[] S, int[][] B, int n, int m) {
		int y, l;
		
		if (i < n - 1) {
			y = i + 1;
			while ( y < n - 1 && S[y].charAt(j) != 'X') {
				y++;
			}

			l = Math.max(B[i][j], y - i);
			
			if (l < B[y][j]) {
				updatePlatform(y, j, l, S, B, n, m);
			}
		}
		
		if (i > 0) {
			y = i - 1;
			while (y > 0 && S[y].charAt(j) != 'X') {
				y--;
			}
			if (S[y].charAt(j) != 'X')
				return;
			
			l = Math.max(B[i][j], i - y);
			
			if (l < B[y][j]) {
				updatePlatform(y, j, l, S, B, n, m);
			}
		}
	}
	
	public int shortestLadder(String[] level, int coinRow, int coinColumn) {
		
		int n = level.length;
		int m = level[0].length();
		
		int[][] B = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				B[i][j] = Integer.MAX_VALUE;
			}
		}

		updatePlatform(n-1, 0, 0, level, B, n, m);
		
		return B[coinRow-1][coinColumn-1];
	}
	
	public static void main(String[] args) {
		String[] S = new String[]
				{".XXXX.X....XX.X.XX..XXXXX..X..X.XX.X........", "..X.XX..XX...X..XXX.X.XX..X..XXX.....X..XX.X", "..XX...X.XXXXX...X.......X..X...XX..XXX.X.X.", "XXXXXXX.....X.X...XX.XXXXX..X.XX.XXXX.X.....", "...X.XX..X..XXX.X..XXXXX.XXXXXX...X...X..XXX", ".X.XXX.XXXX....X....XX...XX..X.XXXXX.X.X.X..", "....X.XXXX...X..XXXXX..X.X.XXXXXXXXX.X..XX..", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"};
		
		ArcadeManao r = new ArcadeManao();
		System.out.println(r.shortestLadder(S, 2, 31));
		
	}
}
